// 5. 最长回文子串
/**
 * @param {string} s
 * @return {string}
 */


// 中心扩散
/**
 * 两种情况
 * 一种是回文子串长度为奇数(aba 中心是b)
 * 一种是回文子串长度为偶数(abba,中心是 bb)
 * */
var longestPalindrome = function (s) {
    if (s.length < 2) return s
    let l = 0, r = 0
    for (let i = 0; i < s.length; i++) {
        // 回文子串长度是奇数
        helper(i, i)
        // 回文子串长度是偶数
        helper(i, i + 1)
    }
    function helper (m, n) {
        while (m >= 0 && n < s.length && s[m] === s[n]) {
            m--
            n++
        }
        /* 
            注意此处m,n 的值循环完后，是恰好不满住循环条件的时刻
            此时m到n的距离为 n - m + 1 但是 mn 两个边界不能取，所以应该取到 m + 1 到 n - 1的区间
            长度为 n - m - 1
        */

        if (n - m - 1 > r - l - 1) {
            r = n
            l = m
        }
    }

    return s.slice(l + 1, r)
}

// dp
var longestPalindrome = function (s) {
    if (s.length == 0) return ''
    let res = s[0]
    const dp = []
    // 从后向前判断回文，逐步延伸字符串
    for (let i = s.length - 1; i >= 0; i--) {
        dp[i] = []
        for (let j = i; j < s.length; j++) {
            // case:a
            if (j - i === 0) dp[i][j] = true
            // case:aa
            else if (j - i === 1 && s[j] === s[i]) dp[i][j] = true
            // 去掉首尾
            // 一个回文字符串 去掉首位还是回文
            /**
             * P(i,j) = P(i + 1,j - 1) ^ (S[i] === s[j]) 
            */
            else if (s[i] === s[j] && dp[i + 1][j - 1]) dp[i][j] = true
            // update res
            if (dp[i][j] && j - i + 1 > res.length) {
                res = s.slice(i, j + 1)
            }
        }
    }
    return res
};
longestPalindrome("babad")